from functools import lru_cache
from os import startfile
import time


# 统计运行时长
def time_spent(func):
    def run(*args, **kwargs):
        start = time.time()
        ret = func(*args, **kwargs)
        end = time.time()
        print("{0}函数执行耗时: {1}".format(func.__name__, end - start))
        return ret
    return run


# 递归写法很容易超时
def fibo_01(n):
    if n < 1:
        return 0
    if n == 1:
        return 1

    return fibo_01(n-1) + fibo_01(n-2)

# 加上记忆化搜索
@lru_cache()
def fibo_02(n):
    if n < 1:
        return 0
    if n == 1:
        return 1

    return fibo_02(n-1) + fibo_02(n-2)

# 采用循环的方式计算
@time_spent
def fibo_03(n):
    if n < 1:
        return 0
    f1 = 0
    f2 = 1
    for _ in range(n-1):
        f1, f2 = f2, f2 + f1

    return f2


# 采用矩阵快速幂的方式计算
@time_spent
def fibo_04(n):
    """
    [[f(n), f(n-1)],[f(n-1), f(n-2)]] = [[1, 1],[1, 0]] ** (n - 1)
    7(10) == 111(2)
    2 ** 7 = (2 ** 1) * (2 ** 2) * (2 ** 4)
    """
    if n < 1:
        return 0
    base = [[1, 1],[1, 0]]
    n -= 1
    # 单位矩阵
    ans = [[1, 0],[0, 1]]
    row = 2
    col = 2

    while n:
        if n & 1:
            # 临时存储结果的矩阵
            tmp_arr = []
            # 矩阵乘法
            for i in range(row):
                tmp_row = []
                for j in range(col):
                    num = 0
                    for k in range(col):
                        # 现在计算位置(i, j)
                        num += ans[i][k] * base[k][j]
                    tmp_row.append(num)
                tmp_arr.append(tmp_row)
            # 计算完，复制给ans
            ans = tmp_arr
        # n 右移1位
        n >>= 1

        # base与自己相乘
        tmp_arr = []
        # 矩阵乘法
        for i in range(row):
            tmp_row = []
            for j in range(col):
                num = 0
                for k in range(col):
                    num += base[i][k] * base[k][j]

                tmp_row.append(num)
            tmp_arr.append(tmp_row)
        # 计算完，复制给base
        base = tmp_arr

    return ans[0][0]

if __name__ == "__main__":
    n = 50

    start = time.time()
    fibo_01(n)
    print("{0}函数执行耗时: {1}".format("fibo_01", time.time() - start))

    start = time.time()
    fibo_02(n)
    print("{0}函数执行耗时: {1}".format("fibo_02", time.time() - start))

    fibo_03(n)
    
    fibo_04(n)